package z_exam;

/**
 * @Author: 海琳琦
 * @Date: 2022/8/31 17:11
 */
public class 背包模板 {
    public static void main(String[] args) {
        int[] weight = {8, 11, 14, 5, 9, 5};
        int[] value = {20, 15, 40, 10, 25, 30};
        int[] dp = new int[31];
        // 遍历物品
        for(int i = 0; i < weight.length; i++) {
            // 遍历背包容量(每个物品只能用一次，所以倒序遍历)
            for(int j = 30; j >= weight[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        System.out.println(dp[dp.length - 1]);
    }
}
